#include <stdio.h>
#include <stdlib.h>

int main() {
    // step 1# 处理输入数据：n 个物品的价值和重量
    int n, bagsize;
    scanf("%d %d", &n, &bagsize);
    int *weight = (int *)malloc(sizeof(int) * n);
    int *value = (int *)malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &weight[i]);
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &value[i]);
    }
    // step 2# 初始化 dp 数组
    int **dp = (int **)malloc(sizeof(int *) * n);
    for(int i = 0; i < n; i++) {
        dp[i] = (int *)malloc(sizeof(int) * (bagsize + 1));
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= bagsize; j++) {
            dp[i][j] = 0;
        }
    }
    // error 1# j >= wight[0] 而不是 weight[j]
    for(int j = 1; j <= bagsize; j++) {
        if (weight[0] <= j) {
            dp[0][j] = value[0];
        }
    }
    // step 3# 确定递推公式并遍历递推公式
    // error 2# 遍历 dp 数组的时候，注意不要从 0 开始，自己手动推导验证一下，不要负向越界
    for(int i = 1; i < n; i++) {
        for(int j = 1; j <= bagsize; j++) {
            if (j < weight[i]) {
                dp[i][j] = dp[i-1][j];
            }
            else {
                dp[i][j] = dp[i-1][j] > (dp[i-1][j-weight[i]] + value[i]) ?
                dp[i-1][j] : (dp[i-1][j-weight[i]] + value[i]);
            }
        }
    }

    printf("%d", dp[n-1][bagsize]);
    // step 4# 释放内存
    free(value);
    free(weight);
    for(int i = 0; i < n; i++) {
        free(dp[i]);
    }
    free(dp);

    return 0;
}

/* 压缩成一维数组 */
#include <stdio.h>
#include <stdlib.h>

// step 1# 取最大值函数
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int M, N;

    // step 2# 输入物品数量M和背包容量N
    scanf("%d %d", &M, &N);

    // step 3# 动态分配物品的体积数组costs和价值数组values
    int *costs = (int *)malloc(sizeof(int) * M);
    int *values = (int *)malloc(sizeof(int) * M);

    // step 4# 读取每个物品的体积（占用空间）
    for (int i = 0; i < M; i++) {
        scanf("%d", &costs[i]);
    }

    // step 5# 读取每个物品的价值
    for (int i = 0; i < M; i++) {
        scanf("%d", &values[i]);
    }

    // step 6# 创建dp数组，大小为N+1，并初始化为0
    int *dp = (int *)malloc(sizeof(int) * (N + 1));
    for (int i = 0; i <= N; i++) {
        dp[i] = 0;
    }

    // step 7# 遍历每一个物品
    for (int i = 0; i < M; ++i) {
        // step 7.1# 从大到小逆序遍历背包容量（保证每个物品只能使用一次）
        for (int j = N; j >= costs[i]; --j) {
            // step 7.2# 状态转移方程，放或不放当前物品，取最大值
            dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);
        }
    }

    // step 8# 输出最大价值
    printf("%d\n", dp[N]);

    // step 9# 释放动态分配的内存
    free(costs);
    free(values);
    free(dp);

    return 0;
}
